//
// Created by CodeZijun on 2022/12/4.
//

#include "Haffman.h"
//从大到小快排
void quick_sort(vector<haffmanNode*> &vec, int l, int r){
    if(l>=r) return;
    int i = l - 1;
    int j = r + 1;
    int x = vec[l+r>>1]->p.first;
    while(i<j){
        do i++;while(vec[i]->p.first > x);
        do j--;while(vec[j]->p.first < x);
        if(i<j) swap(vec[i], vec[j]);
    }
    quick_sort(vec,l,j);
    quick_sort(vec,j+1,r);
}
//构造haffman树
void haffman::produceHaffManTree() {
    int weight=0;
    string data="";
    vector<haffmanNode*> vec;
    while(true){
        cin>>weight;
        if(weight == -1)
            break;
        cin>>data;
        haffmanNode* h = new haffmanNode(weight,data);
        vec.push_back(h);
    }
    quick_sort(vec,0,vec.size()-1);
    for(int i = 0; i<vec.size() ;i++)
        cout<<vec[i]->p.second<<" ";
    cout<<endl;
    while(vec.size()>1){
        quick_sort(vec,0,vec.size()-1);
        haffmanNode* h = new haffmanNode;
        h->l_child = vec.back();
        vec.pop_back();
        h->r_child = vec.back();
        vec.pop_back();
        h->p.first = h->l_child->p.first + h->r_child->p.first;
        WPL += h->p.first;
        vec.push_back(h);
        quick_sort(vec,0,vec.size()-1);
    }
    root = vec[0];
}

//解码左0右1
string haffman::decipher(string code) {
    int i = 0;
    string ans = "";
    while(i<code.length()){
        haffmanNode* p = root;
        while(p->l_child != nullptr && p->r_child != nullptr){
            if(code[i] == '0')
                p = p->l_child;
            else if (code[i] == '1')
                p = p->r_child;
            i++;
        }
        ans += p->p.second;
    }
    return ans;
}